public class InversePairs {
    // 数组中的逆序对
    // https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    private int[] tmp;
    public int InversePairs (int[] nums) {
        // write code here
        tmp = new int[nums.length];
        return merge(nums, 0, nums.length-1);
    }

    private int merge(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        long ret = 0;
        ret += merge(nums, left, mid);
        ret += merge(nums, mid + 1, right);
        int index1 = left, index2 = mid + 1;
        int i = 0;
        while (index1 <= mid && index2 <= right) {
            if (nums[index1] > nums[index2]) {
                ret += mid - index1 + 1;
                tmp[i++] = nums[index2++];
            } else {
                tmp[i++] = nums[index1++];
            }
        }
        while (index1 <= mid) {
            tmp[i++] = nums[index1++];
        }
        while (index2 <= right) {
            tmp[i++] = nums[index2++];
        }
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j-left];
        }
        return (int)(ret % 1000000007);
    }
}
